package com.jp.algorithm.graph;

import java.util.*;

public class MyGraph {

    Map<Integer,Vertex> map;

    public MyGraph(){
        map = new HashMap<>();
    }

    class Vertex{
        int val;
        int inDegree;
        int outDegree;
        List<Edge> edges;

        public Vertex(int val){
            this.val=val;
            inDegree=0;
            outDegree=0;
            edges=new ArrayList<>();
        }
    }

    class Edge{
        Vertex end;
        int weight;

        public Edge(int end,int weight){
            this.end=map.get(end);
            this.weight = weight;
        }
    }

    public void addVertext(int val){
        if(map.get(val) == null){
            map.put(val,new Vertex(val));
        }
    }
    public void addEdge(int start, int end, int weight){
        if(map.get(start) == null){
            addVertext(start);
        }
        if(map.get(end) == null){
            addVertext(end);
        }

        map.get(start).edges.add(new Edge(end,weight));
        map.get(end).inDegree++;
        map.get(start).outDegree++;
    }

    public void print(){
        for (Vertex vertex : map.values()){
            for(Edge edge : vertex.edges){
                System.out.println("start:"+vertex.val+",end:"+edge.end.val+",weight:"+edge.weight);
            }
        }
    }

    public void topSort(){
        //存储入度的map
        Map<Integer,Integer> inDegreeMap = new HashMap<>();
        for(Map.Entry<Integer,Vertex> entry : map.entrySet()){
            inDegreeMap.put(entry.getKey(),entry.getValue().inDegree);
        }

        while(!inDegreeMap.isEmpty()){
            //找到一个入度为0的节点
            int val = findZeroInDegree(inDegreeMap);
            //没找到，说明有圈
            if(val == -1)
                return ;
            else{
                //输出当前节点
                System.out.println(val);
                //每个相连的节点入度减1
                for(Edge edge : map.get(val).edges){
                    inDegreeMap.put(edge.end.val,inDegreeMap.get(edge.end.val)-1);
                }
                //从入度hash中删除当前节点
                inDegreeMap.remove(val);
            }

        }

    }
    private Integer findZeroInDegree(Map<Integer,Integer> map){
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() == 0)
                return entry.getKey();
        }
        return -1;
    }


    public  int shortestPathWithNoWeight(int startVal, int endVal){

        Queue<Integer> queue = new LinkedList<>();
        Map<Integer,DistRecord> recordMap = new HashMap<>();
        queue.add(startVal);
        recordMap.put(startVal,new DistRecord(0,-1));
        while(!queue.isEmpty()){
            int cur = queue.poll();
            if(cur == endVal){
                return recordMap.get(cur).dist;
            }else{
                for(Edge edge: map.get(cur).edges){
                    int endValue = edge.end.val;
                    if(recordMap.get(endValue) == null){
                        queue.offer(edge.end.val);
                        DistRecord record =  new DistRecord(recordMap.get(cur).dist+1,cur);
                        recordMap.put(endValue,record);
                    }
                }
            }
        }
        return -1;
    }

    public void dijkstra(int startVal){
        Map<Integer,DistRecord> distMap = new HashMap<>();
        distMap.put(startVal,new DistRecord(0,0));
        for(Map.Entry<Integer,Vertex> entry : map.entrySet()){
            if(entry.getKey() != startVal){
                distMap.put(entry.getKey(),new DistRecord(9999,0));
            }
        }

        while(true){

            int minVal = fineMin(distMap);
            System.out.println("Val:"+minVal);
            distMap.get(minVal).known=true;

        }

    }
    public int fineMin(Map<Integer,DistRecord> distMap){
        int min=9999;
        for (Map.Entry<Integer,DistRecord> entry : distMap.entrySet()){
            if(!entry.getValue().known && entry.getValue().dist < min){
                min=entry.getKey();
            }
        }
        return min;
    }
    class DistRecord{
        int dist;
        int parent;
        boolean known=false;
        public DistRecord(int dist,int parent){
            this.dist=dist;
            this.parent=parent;
        }
    }

    public static  void  testTopSort(){
        MyGraph myGraph = new MyGraph();
        myGraph.addEdge(0,1,0);
        myGraph.addEdge(1,2,0);
        myGraph.addEdge(2,3,0);
        myGraph.print();
        myGraph.topSort();
    }
    public static void main(String[] args) {
        testTopSort();
    }

}
